1975D - Paint the Tree - CodeForces Solution

from collections import deque, defaultdict

def bfs(start):
    dist = [-1] * (n+1)
    dist[start] = 0
    q = deque()
    q.append(start)
    while q:
        v = q.popleft()
        for child in graph[v]:
            if dist[child] == -1:
                dist[child] = dist[v] + 1
                q.append(child)
    return dist

t = int(input())
for _ in range(t):
    n = int(input())
    a, b = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(n-1):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)
    dist = bfs(a)
    path = [b]
    x = b
    while x != a:
        for parent in graph[x]:
            if dist[parent] < dist[x]:
                x = parent
                path.append(x)
                break
    m = len(path)
    dist = bfs(path[m//2])
    ans = m // 2
    ans += 2*(n-1) - max(dist)
    print(ans)